package bin_tree.MinHeap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class MinHeap {
    List<Integer> data;

    public MinHeap(int size){
        data = new ArrayList<>(size);
    }

    //堆化
    public MinHeap(int arr[]){
        data = new ArrayList<>(arr.length);
        for (int i : arr) {
            data.add(i);
        }
        for (int i = pareat(data.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public MinHeap(){
        this(10);
    }

    //判空
    public boolean isEmpty(){
        return data.size() == 0;
    }

    //根据K的索引找到父节点的索引
    private int pareat(int k){
        return (k - 1) >> 1;
    }

    //根据根据K的索引找到左子树节点的索引
    private int leftChild(int k){
        return (k << 1) + 1;
    }

    //根据根据K的索引找到右子树节点的索引
    private int rightChild(int k){
        return (k << 1) + 2;
    }

    //添加
    public void add(int val){
        data.add(val);
        siftUp(data.size() - 1);
    }

    //取出堆顶元素
    public int extractMin(){
        if(isEmpty()){
            throw new NoSuchElementException("Heap is empty!extract false!");
        }
        int minNum = data.get(0);
        data.set(0,data.get(data.size() - 1));
        data.remove(data.size() - 1);
        siftDown(0);
        return minNum;
    }

    //下沉
    private void siftDown(int k) {
        while (leftChild(k) < data.size()){
            int minNUm = leftChild(k);
            if(minNUm + 1 < data.size() && data.get(minNUm) > data.get(minNUm + 1)){
                minNUm = minNUm + 1;
            }
            if(data.get(k) <= data.get(minNUm)){
                break;
            }else{
                swap(k,minNUm);
                k = minNUm;
            }
        }
    }

    //上浮
    private void siftUp(int k) {
        while(k > 0 && data.get(k) < data.get(pareat(k))){
            //交换当前节点和父节点的值
            swap(k,pareat(k));
            k = pareat(k);
        }
    }

    //交换
    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }

    @Override
    public String toString() {
        return data.toString();
    }
}
